The present invention relates, in general, to error detection/correction and fault detection/recovery, and, in particular, to digital data error correction using forward correction by block code for determining synchronization.
To encode a signal of a user-definable length using forward error correction, a user first determines the number of bits k of the signal that will be encoded per codeword. The variable k is often referred to as the number of information bits per codeword.
Next, the user determines the length n of the codewords. Each codeword is the same length. The length of the codeword determines the amount of redundancy that is added to the information bits. The values of the redundant bits are a function of the information bits and, therefore, provide information on the true value of the information bits. Therefore, the redundant bits may be used to determine the true value of the information bits and, therefore, correct the information bit if the information bit is not the true value. The amount of redundancy introduced into a codeword is proportional to the number of errors that may be corrected. An error in a codeword is a bit in the codeword that is not correct (i.e., a 0 when it should be a 1, or vice versa). Typically, errors are introduced into a codeword during the transmission of the codeword. The source of the error is often equipment malfunction or noise in the transmission channel. Greater redundancy provides greater information on the true value of the information bits and, therefore, provides lesser dependence on any single bit for the true value of an information bit. A lesser dependence on a single bit for the true value of an information bit increases the number of errors that can be withstood (i.e., corrected) by the codeword.
Next, the user selects a k by n generator matrix G. Procedures exist for each prior art encoding scheme for selecting a generator matrix once k and n have been established.
Next, the user selects k bits from the signal to be encoded and multiplies these bits by the generator matrix G to produce an n-bit codeword. If k is 3 and n is 6 then G is a 3xc3x976 matrix, where 3 signal bits will be used to generate each codeword, and each codeword will be 6 bits long. In this example, 3 information bits are encoded to form a 6-bit codeword. So, the codeword contains 3 redundant bits that may be used to determine the true values of the 3 signal bits even in the presence of a certain maximum number of errors introduced into the codeword. For example, a signal to be encoded is 001010011100101110111, where k is 3, n is 6 and G is as follows.   G  =      [                            1                          0                          0                          1                          0                          1                                      0                          1                          0                          1                          1                          0                                      0                          0                          1                          0                          1                          1                      ]  
The signal is then divided into 3-bit segments (i.e., 001, 010, 011, 100, 101, 110, and 111). Each segment is then multiplied by G to form the following 6-bit codewords, respectively: 001011, 010110, 01110101, 10001, 101110, 110011, and 111000.
The generator matrix G, which is based on k and n, sets the maximum number of errors that the codeword generated therefrom can withstand.
The bit location at which a codeword begins is referred to as a codeword boundary. The receiver that will receive an encoded signal must know where is the codeword boundary in order to properly identify the bits of each codeword. Once the codeword boundary is known then the codewords may be decoded to recover the unencoded signal.
A prior art method of determining codeword boundary is to insert a known bit pattern, or marker, between the codewords prior to transmission. The receiver, which must know beforehand what is the marker, checks the received transmission for occurrences of the marker and assumes that each occurrence indicates a codeword boundary. The codewords are then identified and decoded accordingly. A first disadvantage of this method is that adding a marker between each codeword requires more bits to be transmitted and, therefore, reduces the effective transmission rate of the codewords. For example, if a marker is equal to the length of a codeword then half of the bits transmitted correspond to markers and half of the bits transmitted correspond to codewords. So, the codeword transmission rate for this example is half that of transmitting codewords without markers. A second disadvantage of this method is that an error in a marker may cause a codeword boundary to not be recognized as such and, therefore, cause the received transmission to be decoded improperly. A prior art method of lessening the effect of the second disadvantage is to add error correction to the marker. Adding error correction to a marker increases its bit length and, therefore, further reduces the codeword transmission rate.
U.S. Pat. No. 4,389,636, entitled xe2x80x9cENCODING/DECODING SYNCHRONIZATION TECHNIQUE,xe2x80x9d discloses a device for and method of synchronization that encodes each signal bit as a complementary-bit-pair. Encoding each signal bit as a complementary-bit-pair reduces the codeword transmission rate and does not achieve the maximum codeword transmission rate as does the present invention which does not encode each signal bit as a complementary-bit-pair. U.S. Pat. No. 4,389,636 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 4,959,834, entitled xe2x80x9cWORD SYNCHRONIZATION SYSTEM AND METHOD,xe2x80x9d discloses a device for and method of synchronization that calculates a syndrome, sends synchronization pulses, changes the phase of the received signal, and recalculates the syndrome if the first syndrome calculation is not as expected (i.e., zero). The present invention does not calculates a syndrome, send synchronization pulses, and change the phase of the received signal as does U.S. Pat. No. 4,959,834. U.S. Pat. No. 4,959,834 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,761,249, entitled xe2x80x9cSYNCHRONIZATION ARRANGEMENT FOR DECODER/DE-INTERLEAVER,xe2x80x9d discloses a device for and method of synchronization that requires the inclusion of periodic decoder synchronization signals in the received signal (i.e., markers). The present invention does not require the inclusion of a marker to indicate codeword boundary. U.S. Pat. No. 5,761,249 is hereby incorporated by reference into the specification of the present invention.
It is an object of the present invention to determine the codeword boundary of an encoded signal transmitted without marker bits for indicating codeword boundary.
It is another object of the present invention to determine the codeword boundary of an encoded signal transmitted without marker bits for indicating codeword boundary by calculating a dot product of at least one codeword and at least one vector of a dual of the code used to encode the signal.
It is another object of the present invention to determine the codeword boundary of an encoded signal transmitted without marker bits for indicating codeword boundary by calculating a dot product of at least one codeword and at least one vector of a dual of the code used to encode the signal even if the encoded signal includes more errors than the code was designed to withstand.
The present invention is a method of determining the starting bit position of a codeword (i.e., the codeword boundary) that does not require the use of marker bits to identify the codeword boundary.
The first step of the method is receiving a plurality of transmission bits. The transmission bits include at least one codeword.
The second step of the method is determining the dual code of a code used to generate the at least one codeword in the transmission bits.
The third step of the method is selecting a vector from the dual code, excluding an all-zeros vector.
The fourth step of the method is initializing n scoring variables Sz each to zero, where 1xe2x89xa6zxe2x89xa6n.
The fifth step of the method is initializing i=1.
The sixth step of the method is initializing z=1.
The seventh step of the method is selecting n bits from the received transmission bits ti for processing, starting at bit position i.
The eighth step of the method is performing an AND operation on the vector selected and the n bits selected from the received transmission bits on a bit-by-bit basis without any carry over from one bit position to another. This is commonly referred to as a bit-wise AND operation.
If the result of the eighth step contains an even number of ones then the ninth step of the method is assigning a value of zero to the result of the last step. Otherwise assigning a value of one to the result of the last step. The eighth step is commonly referred to as a dot product.
The tenth step of the method is setting Sz equal to Sz plus the result of the ninth step.
If the present value of z is less than n, the eleventh step of the method is incrementing z and i each by 1 and returning to the seventh step. Otherwise, proceeding to the next step.
If z=n, i less than L, and it is desired to process additional transmission bits then the twelfth step is incrementing i by 1, and returning to the sixth step. Otherwise proceeding to the next step.
The thirteenth step of the method is identifying the scoring variable Sz having the lowest score.
The fourteenth, and last, step of the method is identifying the subscript z of the result of the thirteenth step as the codeword boundary.